Address correlations can be used to predict the addresses of future instructions to be referenced during execution of code within a processing unit. This form of address speculation is useful in applications such as cache pre-fetching or instruction scheduling. A simple address-address correlation consists of a key and successor value pair. A predictor that uses address-address correlation observe the previous address pairs, stores them, and uses them as predictions of future addresses. The correlations are typically stored in a correlation prediction table indexed by the key. The current address value is used as the key to retrieve the corresponding correlation and successor value predicts the future address.
For example, when used with cache pre-fetching, address-address correlations are built from the cache miss addresses to predict future miss addresses. When a cache miss is generated, the preceding cache miss address and the current cache miss address are stored in a correlation prediction table as a key and successor value pair. The next time the key address generates a cache miss, the corresponding entry in the correlation prediction table predicts that the successor address will be the next cache miss.
The basic address-address correlation scheme has been extended to allow for multiple correlation value addresses to increase prediction accuracy. In these multiple value address correlations, the correlation values are maintained with an least-recently-used replacement policy and the successor value addresses are pre-fetched with a most-recently-used priority.
To maximize the opportunity for hiding memory access latency with cache pre-fetching, the pre-fetch should be initiated such that the data arrives in a timely manner. Traditionally, pre-fetching data from the cache too early was a concern. If the data is pre-fetched too early, the pre-fetched data might displace other useful data from the cache, or the pre-fetched data itself might be displaced by other references before the pre-fetched data can be used. Conversely, if the pre-fetch is not initiated sufficiently ahead of when the data is required, the inherent latency of the memory will not be hidden. Given the trend of increasing relative memory latency, the issue is no longer whether the pre-fetching is too early but whether the pre-fetching is early enough to hide the long memory latency.
Although increasing the correlation distance, i.e., the number of references between addresses from which correlations are built, increases the timeliness of correct predictions for address-address correlations, it has a significant adverse effect on the absolute number of correct predictions. Thus, current address-address correlation schemes are unable to initiate pre-fetches early enough to hide long memory latencies without sacrificing prediction coverage.